\documentclass{article}
\usepackage{amssymb,amsmath} % import math
\usepackage[german]{babel} % import german
\usepackage[applemac]{inputenc} % import german apple
\usepackage{graphicx} % import graphics
\usepackage[babel,german=quotes]{csquotes} % quoting

\title{HA2 - Uebung 2}
\author{Leonardo Balestrieri, Marco Traeger}

% some newdefs for math symbols
\newcommand{\lfollow}{\rightarrow} % logical follow
\newcommand{\sfollow}{\Longrightarrow} % semantic follow
\newcommand{\siff}{\iff} % semantic iff
\newcommand{\lAnd}[2]{\bigwedge_{#1}^{#2}} % big and
\newcommand{\lOr}[2]{\bigvee_{#1}^{#2}} % big or

\newcommand{\Oc}[2]{\overset{#1}{#2}}
\newcommand{\Uc}[2]{\underset{#1}{#2}}
\newcommand{\OC}[2]{\Oc{#1}{\overbrace{#2}}}
\newcommand{\UC}[2]{\Uc{#1}{\underbrace{#2}}}
\newcommand{\case}[1]{\quad Fall #1 :\\\\}

\begin{document}
\parindent 0pt %keine Zeileneinrueckungen

\maketitle

\subsection*{2.1a}

$$
A x = b \siff 
\begin{matrix} 
	a_{11} \land x_1 \lor 	& \cdots	& \lor a_{1n} \land x_n = b_1 \sim \text{Zeile } z_1 \\
	\vdots 			& \ddots	& \vdots \\
	a_{k1} \land x_1 \lor 	& \cdots 	& \lor a_{kn} \land x_n = b_k \sim \text{Zeile } z_k\\
\end{matrix}
$$

Wir w"ahlen Zeilen $z_i$ mit $b_i = 0$. Aus
\begin{equation}
\begin{split}
b_i = 0 	& \sfollow a_{i1} \land x_1 \lor \cdots \lor a_{in} \land x_n = 0 \\
		& \sfollow a_{ij} = 0 \sfollow x_j = 0 \forall j
\end{split}
\end{equation}

Sei nun $L = (l_1 \cdots l_n) mit$
$$
l_i = \begin{cases}
		0 & \text{wenn } \exists \text{ Zeile $z_i$ mit $b_i = 0$ aus der $x_j = 0$ folgt} \\
		1 & \text{sonst }
	\end{cases}
$$
$L$ ist unser L"oesungsvektor f"ur $x$.

Da jede Zeile $n$ Variablen enth"alt und es maximal $k$ Zeilen gibt, k"onnen wir $L$ in $O(n \cdot k)$ berechnen.
\\ \\

Wir pr"ufen nun f"ur jede \enquote{1-Zeile} $z_i$ ob $a_{i1}l_1 \lor \cdots \lor a_{in}l_n = 1$, falls dies f"ur eine Zeile nicht gilt, gibt
es keine L"osung f"ur das BGS; sonst ist $L$ ein L"osungsvektor f"ur $Ax = b$. Wiederum ist dieser Teil in $O(n \cdot k)$ berechenbar.
\\
Damit ist die L"osung eins BGL in $O(n \cdot k)$ berechenbar.
\\

Es bleibt noch zu zeigen. Falls $AL \neq b$ $\sfollow$ BGS $Ax=b$ hat keine L"osung
$$\siff$$
$Ax = b$ hat L"osung $y$ $\sfollow$ $AL=b$.

$ $\\ \\
Beweis: Sei $y$ L"osung von $Ax = b$ daher es gilt
$$
\forall i : a_{i1} \land y_1 \lor \cdots \lor a_{in} \land y_n = b_i
$$

\case{$b_i = 0$}
dann gilt f"ur $a_{ij} = 1 \sfollow y_j = 0 = l_j$ nach Konstruktion, 
daher aber auch 
\begin{equation}
\begin{split}
		& l_j = 0 \lfollow y_j = 0 ^{[1]} \\
\sfollow	& \lOr{j}{} a_{ij} \land l{j} = 0 = b_i
\end{split}
\end{equation}

\case{$b_i = 1$}
\begin{equation}
\begin{split}
		& a_{i1}y_1 \lor \cdots \lor a_{in}y_n = b_i \\
\sfollow 	& \exists y_j, a_{ij} : y_j = 1\land a_{ij} = 1 \Oc{[1] \sfollow y_j = 1 \lfollow l_j = 1}{\sfollow} l_j = 1 \\
\sfollow 	& \lOr{j}{} a_{ij} \land l{j} = 1 = b_i
\end{split}
\end{equation}

$\sfollow$	$L$ ist L"osung f"ur $Ax = b$

\subsection*{2.1b}

Die L"osungsmethode ist Analog zu $2.1a$, nur das wir bei der "Uberpr"ufung der \enquote{0-Zeilen} pr"ufen m"ussen ob
sich die Belegungen f"ur ein $x_j$ wiedersprechen. Daher wir interpretieren $\lnot x_j$ als eine neue Variable $q_j$. Damit
ist $x = (x_1, \cdots , x_n, \lnot x_1, \cdots, \lnot x_n) = (x_1, \cdots , x_n, q_1, \cdots, q_n)$. Nun f"uhren wir den 1. Schritt des Algorithmusses aus,
die Bestimmung von L.
\\ \\
Nun pr"ufen wir ob ein $l_j = 0 = l_{j + n}$ existiert mit $j \leq n$. Falls ein solches $j$ existiert, dann gilt: $0 = x_j = q_j = \lnot x_j$, und damit hat das BGL keine L"osung.
Diese "Uberpr"ufung ist in O(2n) m"oglich.
\\ \\
Wenn ein solches $j$ nicht gefunden wurde, kann das $L$ eine L"osungen sein. wir m"ussen nur wie in $2.1a$ pr"ufen ob die \enquote{1-Zeilen} erf"ullt sind. Dies geschieht
genau analog zu $2.1a$.
\\ \\
Wenn es eine L"osung f"ur das BGL gibt, dann konstruiert der Algorithmus auch ein $L$ das L"osung f"ur das BGL ist, Beweis analog zu $2.1a$.
\\ \\
Die Gesamtlaufzeit ist hier daher $O(2n \cdot k)$.

\subsection*{2.2a}

Wir sollen zeigen: ist der transitive Abschluss von $n \times n$ Matrizen in $A(n)$ Operationen berechenbar $\sfollow$
die boolsche Matrixmultiplikation ist mit A(3n) Operationen berechenbar.

Wir konstruieren einen Graphen $G$ der aus den 3 Kantenmengen $V_1, V_2, V_3 \in V$ mit jeweils der Gr"o"se $n$ besteht und 
dessen Kanten folgenderma"sen bestimmt sind:
\begin{itemize}
\item Kanten von $V_1$ nach $V_2$ die durch $A$ beschrieben werden, wenn wir $A$ als Adjazenzmatrix interpretieren 
\item Kanten von $V_2$ nach $V_3$ die durch $B$ beschrieben werden, wenn wir $B$ als Adjazenzmatrix interpretieren 
\end{itemize}

Damit ergibt sich folgende Adjazenzmatrix $M_G$ des konstruiereten Graphen $G$:
$$
M_G = \begin{pmatrix}I & 0 & 0 \\ A & I & 0 \\ 0 & B & I\end{pmatrix}
$$
Und ihr transitiver Abschluss
$$
{M_G}^* = \begin{pmatrix}I & 0 & 0 \\ A & I & 0 \\ 0 & B & I\end{pmatrix}^* 
= \begin{pmatrix}I^* & 0 & 0 \\ I^*AI^* & I^* & 0 \\ I^*AI^*BI^* & I^*BI^* & I*\end{pmatrix}
$$
$$
= \begin{pmatrix}I & 0 & 0 \\ IAI & I & 0 \\ IAIBI & IBI & I\end{pmatrix}
= \begin{pmatrix}I & 0 & 0 \\ A & I & 0 \\ AB & B & I\end{pmatrix}
$$

Damit steht das Ergebniss der Multiplikation von $A$ und $B$ im unteren Drittel des transitiven Abschlusses $M^*$.
$M^*$ ist eine $3n \times 3n$ Matrix und damit ben"otigt die Berechnung ihres Transitiven Abschlusses
$A(3n)$ Operationen. Daher ist auch die Matrixmultiplikationen von 2 $n \times n$ Matrizen in $A(3n)$ m"oglich.

\end{document}